#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cassert>

int *preKmp(const char *x) {
		int i, j;
		int m = strlen(x);
		int *next = new int[m];

		i = 0;
		j = next[0] = -1;
		while (i < m) {
				while (j > -1 && x[i] != x[j])
						j = next[j];
				i++;
				j++;
				if (x[i] == x[j])
						next[i] = next[j];
				else
						next[i] = j;
		}
}

void print_next(const char *pattern, int *next) {
	for (int i=0;i<strlen(pattern);i++) {
		std::cout<<std::setw(10)<<std::left;
		std::cout<<i;
	}
	std::cout<<std::endl;

	for (int i=0;i<strlen(pattern);i++) {
		std::cout<<std::setw(10)<<std::left;
		std::cout<<*(pattern+i);
	}
	std::cout<<std::endl;

	for (int i=0;i<strlen(pattern);i++) {
		std::cout<<std::setw(10)<<std::left;
		std::cout<<*(next+i);
	}
	std::cout<<std::endl;
}


void KMP(const char *x, int m, const char *y, int n) {
   int i, j;
   int *next = preKmp(y);

   i = j = 0;
   while (j < n) {
      while (i > -1 && x[i] != y[j])
         i = *(next+i);
      i++;
      j++;
      if (i >= m) {
         printf("%s\n",x+j-i);
         i = *(next+i);
      }
   }
}


int main() {
	const char * pattern = "name";
	int *next=preKmp(pattern);
	print_next(pattern,next);
	
	const char *text = "hello,my name is junix.";
	KMP(text, strlen(text), pattern, strlen(pattern));
}

